// 问题：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
// 解法：位运算/哈希表


// 位运算，记录所有数字二进制中，每个位出现的次数
// 例如：如果数字5出现3次，则
// 0101
// 0101
// 0101
// 每个位对应的次数为：0303，对3取余后结果为0000;

// [3, 3, 5, 3] 对应bit_count（从高位到低位）为[0,1,3,4]；取余后结果为[0,1,0,1]
int singleNumber(int* nums, int numsSize){
    int i, j, bit_count[32] = {0};
    for (i = 0; i < numsSize; i++) {
        for (j = 0; j < 32; j++) {  //记录每个数的二进制
            bit_count[j] += nums[i]&1; 
            nums[i] >>= 1;  //移位
        }
    }

    int res = 0;
    for (i = 31; i >= 0; i--) {
        if (bit_count[i] % 3)   //不为0
            res += (bit_count[i]%3)<<i;
    }
    return res;
}

// 哈希解法
// typedef struct {
//     int key;
//     int cnt;
//     UT_hash_handle hh;
// } uthash_t;

// int singleNumber(int* nums, int numsSize){
//     uthash_t *hash = NULL, *ret;
//     int i, res = 0;
//     for (i = 0; i < numsSize; i++) {
//         HASH_FIND_INT(hash, &nums[i], ret);
//         if (ret == NULL) {
//             uthash_t *temp = malloc(sizeof(*temp));
//             temp->key = nums[i];
//             temp->cnt = 1;
//             HASH_ADD_INT(hash, key, temp);
//         } else {
//             ret->cnt++;
//         }
//     }
//     uthash_t *next;
//     HASH_ITER(hh, hash, ret, next) {
//         if (ret->cnt == 1) {
//             res = ret->key;
//         }
//         HASH_DEL(hash, ret);
//         free(ret);
//     }
//     return res;
// }